//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 
//
// 有效 二叉搜索树定义如下： 
//
// 
// 节点的左子树只包含 严格小于 当前节点的数。 
// 节点的右子树只包含 严格大于 当前节点的数。 
// 所有左子树和右子树自身必须也是二叉搜索树。 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [2,1,3]
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目范围在[1, 10⁴] 内 
// -2³¹ <= Node.val <= 2³¹ - 1 
// 
//
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 2614 👎 0


//leetcode submit region begin(Prohibit modification and deletion)




import java.util.concurrent.atomic.AtomicLong;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
//    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        //二叉搜索树中序遍历是递增的 (判断上下两个变量是否相等）
//        //非递归
//        TreeNode p = root;
//        LinkedList<TreeNode> stack = new LinkedList<>();
//        long prev = Long.MIN_VALUE;
//        while(p!=null || !stack.isEmpty()){
//            if(p!=null){
//                stack.push(p);
//                p = p.left;
//            }else{
//                TreeNode pop = stack.pop();
//                //处理值
//                if(prev >= pop.val){//二叉搜索树中序遍历是递增的，且没有重复元素
//                    return false;
//                }
//                prev = (long)pop.val;
//                p = pop.right;
//            }
//        }
//        return true;
//        > 2025/08/10 01:43:38
//        解答成功:
//        执行耗时:2 ms,击败了18.20% 的Java用户
//        内存消耗:43.5 MB,击败了22.07% 的Java用户



//        //递归
//        if(root == null)
//            return true;
//        boolean leftFlag = isValidBST(root.left);
//        if(!leftFlag) //提前结束递归。
//            return false;
//        if(prev >= root.val ){
//            return false;
//        }
//        prev = (long) root.val;
//        return isValidBST(root.right);
////        > 2025/08/10 01:49:23
////        解答成功:
////        执行耗时:0 ms,击败了100.00% 的Java用户
////        内存消耗:42.5 MB,击败了52.62% 的Java用户
//
////        > 2025/08/10 01:54:12
////        解答成功:
////        执行耗时:0 ms,击败了100.00% 的Java用户
////        内存消耗:42.4 MB,击败了70.97% 的Java用户
//        return  doValid(root, new AtomicLong(Long.MIN_VALUE));
        return doValid2(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
//
//    private boolean doValid(TreeNode root, AtomicLong prev){
//        if( root == null)
//            return true;
//        boolean a = doValid(root.left, prev);
//        if(!a)
//            return false;
//        if(prev.get() >= root.val)
//            return false;
//        prev.set(root.val);
//        return doValid(root.right, prev);
////        > 2025/08/10 02:03:39
////        解答成功:
////        执行耗时:0 ms,击败了100.00% 的Java用户
////        内存消耗:42.5 MB,击败了62.10% 的Java用户
    //上下限递归实现
    private boolean doValid2(TreeNode root, long min, long max) {
        if(root == null)
            return true;
        if(root.val <= min || root.val >= max)
            return false;
        return doValid2(root.left, min, root.val) && doValid2(root.right, root.val, max);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
